package com.yjz.leetcode.快速排序算法.快速排序;

/**
 * @author :yuanJinZhong
 * @description:快速排序 快速排序的算法复杂度是 n*log2N
 * 快速排序的基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。
 * @date :2018/10/22-15:59
 */
public class QuickSort {

  //https://www.cnblogs.com/xiaoming0601/p/5862860.html        (可以看懂的快速排序)

  // https://baike.baidu.com/item/%E5%AF%B9%E6%95%B0%E5%87%BD%E6%95%B0/6013318?fr=aladdin    (对数在数轴上的表示，可以直观看出各个时间复杂度)

  /**
   * @description:将数组一分为二，左边比基准值小，右边比基准值大，并且返回基准值的 index
   * @author :yuanJinZhong
   * @date :2018/10/23-15:04
   */
  public static int getMiddle(int[] arr, int left, int right) {

    int pivot = arr[left];

    //两个指针相遇的时候会推出循环
    while (left < right) {
      //从高位往低位比较，若高位的值比base值大，则比较次高位，若高位值比base值小，则将这个高位值，放到低位
      while (left < right && arr[right] >= pivot) {
        right--;
      }
      //比基准值小的高位值，放到低位
      arr[left] = arr[right];
//			printArr(arr);
      //从低位往高位比较，如果低位值小于base值，则比较次低位，若低位值比base大，则将这个低位值（此处低位值经过++和上一步的低位值已经不是同一个了），放到刚刚的高位（高位经过--，也不是一开始的高位）
      while (left < right && arr[left] <= pivot) {
        left++;
      }
      //比基准值大的低位，放到23行的高位
      arr[right] = arr[left];
//			printArr(arr);
    }

    arr[left] = pivot;
//		printArr(arr);
    return left;
  }


  public static void printArr(int[] arr) {
    for (int i : arr) {
      System.out.print(i + ",");
    }
    System.out.println("\n");
  }


  public static void quickSort(int[] arr, int left, int right) {

    if (left < right) {
      int baseIndex = getMiddle(arr, left, right);

      quickSort(arr, left, baseIndex - 1);

      quickSort(arr, baseIndex + 1, right);
    }
  }

  public static void main(String[] args) {

    int[] arr = new int[]{9, 0, 7, 8, 6, 5, 11, 44, 77, 55, 66};

    quickSort(arr, 0, arr.length - 1);

    printArr(arr);
  }

}
